In communication systems, such as illustrated in FIG. 1, a transmitter 10 sends information to a receiver 12 via a communication channel 14. Of course, for bidirectional communications between two physically separated units, each unit functions alternately as both a transmitter 10 and a receiver 12.
One problem which any communication system has to address is the potential for loss of information in communication channel 14, e.g., due to fading, noise and other communication channel imperfections. In order to reduce the likelihood of such information loss, it has become common in the design of communications systems to encode digital signals to be transmitted. Such encoding typically involves spreading the information contained in the data bits across a greater number of data bits so that if any are lost the information still potentially can be reconstructed. In practice, it is common to use a type of forward error-correction encoding in which the value of each binary output symbol is formed on the basis of multiple input bits.
Once such information spreading has been completed, the resulting symbols typically are interleaved, so as to ensure that correlated information symbols are not immediately adjacent to each other in the time-domain data stream. By so interleaving, the effects of short-term bursts of noise or fading eventually (after subsequent de-interleaving) are distributed over multiple bits. The end result is that the probability that any particular original information bit cannot be recovered at the receiving end is significantly reduced, meaning more accurate reproduction at the receiving side of the communication channel.
One type of forward error-correction encoding that has become prevalent is turbo coding. A simplified block diagram of a system 20 for implementing one example of turbo coding is illustrated in FIG. 2. As shown in FIG. 2, input into system 20 is a sequence of information bits 22 to be communicated. Information bits 22 are supplied directly to first constituent encoder 24 and are supplied to second constituent encoder 28 via temporal interleaver 26. Encoders 24 and 28 are identical. Temporal interleaver 26 is a block interleaver, meaning that it interleaves bits in fixed-length segments (or blocks) such that the bits of each such block are interleaved independently of any other block, but with the interleaving pattern typically being identical across all blocks. The precise details of the operation of interleaver 26 and encoders 24 and 28 are not critical to the present invention and therefore are not discussed here. However, each encoder 24 and 28 outputs two symbols for each input bit. Thus, encoder 24 outputs symbols Y0 and Y1 and encoder 28 outputs symbols Y0′ and Y1′. Output symbol X is identical to the input bit. Accordingly, the X, Y0, Y1, Y0′ and Y1′ symbols (the turbo code) are produced for each input bit.
The turbo code generated in the foregoing manner is first provided to a channel interleaver 30 which interleaves the coded output symbols and sometimes punctures certain of the symbols to insert control signals or other data. Thereafter, the resulting symbols can be processed for transmission, such as by performing quadrature phase-shift keying modulation.
An iterative decoder 50 for decoding the symbols generated by system 20 is illustrated in FIG. 3. Initially, channel de-interleaver 52 zeroes any symbols punctured by channel interleaver 30 and then de-interleaves the symbols in order to reverse the interleaving performed by channel interleaver 30. For each input bit k in a frame of data, the received symbols X, Y0 and Y1, together with a feedback signal {tilde over (L)}(uk), are input into a posteriori probability (APP) decoder 54. On the first iteration performed by decoder 50, {tilde over (L)}(uk) is zero for all values of k. Upon completion of its decoding operation, APP decoder 54 outputs a soft value {tilde over (L)}(ûk) for each value of k. {tilde over (L)}(ûk) is then interleaved in interleaver 56 to provide {tilde over (L)}(un) which in turn is input into APP decoder 58, together with the Y0′ and Y1′ for the current block. The output of APP decoder 58, {tilde over (L)}(ûk), is then de-interleaved in de-interleaver 60. Finally, the output of de-interleaver 60, {tilde over (L)}(uk), is fed back into APP decoder 54, together with the X, Y0 and Y1 for the current block, for the next iteration of processing to be performed by decoder 50.
The foregoing process typically is repeated across multiple iterations. In this regard, it is noted that channel de-interleaver 52 makes available all X, Y0, Y1, Y0′ and Y1′ for each original input bit in the current block. After every iteration, as described above, the soft and feedback values {tilde over (L)}(ûk) and {tilde over (L)}(uk) are added together for each input bit k in adder 62. The output of adder 62, L(ûk), known as the log likelihood ratio (LLR), is then input into hard decision module 64 to provide a final decision for each bit. Typically, hard decision module 64 is implemented as a threshold detector.
As indicated above, turbo decoding requires multiple iterations of constituent code decoding. In general, using a greater number of iterations results in less decoding error. However, for speed and efficiency it often is desirable to reduce the number of iterations to the extent possible. For a packet of data being decoded, it is advantageous for the decoder to stop iteration when it determines that its performance can no longer be improved by further iterations or when a determination has been made that an error-free decoding already has been achieved.
There have been a number of approaches to determining the appropriate stop criteria when performing iterative decoding. However, each has its own drawbacks.